/**
 * 494. 目标和
 */
public class Solution_494 {
    int count = 0;

    /**
     * 方法一：递归
     * <p>
     * 时间复杂度：O(2^N)
     * <p>
     * 空间复杂度：O(N)
     */
    public int findTargetSumWays(int[] nums, int target) {
        calculate(nums, 0, 0, target);
        return count;
    }

    private void calculate(int[] nums, int i, int sum, int target) {
        if (i == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], target);
            calculate(nums, i + 1, sum - nums[i], target);
        }
    }

    public static void main(String[] args) {
        Solution_494 solution = new Solution_494();
        int[] nums = { 1, 1, 1, 1, 1 };
        int target = 3;
        int ans = solution.findTargetSumWays(nums, target);
        System.out.println(ans);
    }
}